/*
Copyright © 2024 weidongkl <weidongkx@gmail.com>
*/

package levenshtein

type Levenshtein struct {
}

func New() *Levenshtein {
	return &Levenshtein{}
}

func (c *Levenshtein) Calculate(s1, s2 string) (float64, error) {
	return LevenshteinSimilarity(s1, s2), nil
}

func (c *Levenshtein) Name() string {
	return "levenshtein"
}

// min returns the minimum of three integers
func min(a, b, c int) int {
	if a <= b && a <= c {
		return a
	}
	if b <= a && b <= c {
		return b
	}
	return c
}

// LevenshteinDistance calculates the Levenshtein distance between two strings
func LevenshteinDistance(s1, s2 string) int {
	// Create a 2D matrix to hold the distances
	d := make([][]int, len(s1)+1)
	for i := range d {
		d[i] = make([]int, len(s2)+1)
	}

	// Initialize the first row and column
	for i := range d {
		d[i][0] = i
	}
	for j := range d[0] {
		d[0][j] = j
	}

	// Fill the matrix
	for i := 1; i <= len(s1); i++ {
		for j := 1; j <= len(s2); j++ {
			if s1[i-1] == s2[j-1] {
				// If the characters are the same, no operation is needed
				d[i][j] = d[i-1][j-1]
			} else {
				// Calculate the minimum of the three possible operations:
				// 1. Insertion
				// 2. Deletion
				// 3. Substitution
				d[i][j] = 1 + min(d[i][j-1], d[i-1][j], d[i-1][j-1])
			}
		}
	}

	// The distance is stored in the bottom-right corner of the matrix
	return d[len(s1)][len(s2)]
}

func LevenshteinSimilarity(s1, s2 string) float64 {
	// Calculate the Levenshtein editDistance between the two strings.
	editDistance := LevenshteinDistance(s1, s2)
	// Check if there was an error in calculating the Levenshtein editDistance. If so, return 0 and the error.
	// Get the length of string s1.
	lenSum := len(s1) + len(s2)
	// If the length of s1 is 0, it means the two strings are identical. Return 1 for maximum similarity.
	if lenSum == 0 {
		return 1
	}
	// Calculate the Levenshtein similarity, which is the difference in lengths divided by the total length.
	// The returned value is a floating-point number representing the similarity of the two strings.
	return float64(lenSum-editDistance) / float64(lenSum)
}
